mit :: ai :: aim :: AIM-254

MASSACHUSETTS INSTITUTE OF TECHNOLOGY
A.I. LABORATORY

January 1970

Artificial Intelligence LOGO

Memo Ho. 254 Memo No. 5

HIM; A Game-Playing Program

Seymour Papert

and
Cynthia Solomon

This work was supported by the National Science Foundation under grant
number GJ-1049 and conducted at the Artificial Intelligence Laboratory,
a Massachusetts Institute of Technology research program supported in
part by the Advanced Research Projects Agency of the Department of Defense
and monitored by the Office of Naval Research under Contract Number
KOflOl 4-70-A-O362-0OO2 .

MHc A Gamc-I'layJ nR Program
by
Seymour Papert and Cynthia Solomon

1.0 Introduction

This note illustrates some Ideas about how to initiate beginning
students into the art of planning and writing a program complex enough to
bo considered a project rather than an exercise on using the language or
simple programing ideas. Hie project is to write a progran to play a
simple game ("one-pile HIM" or "21") as invincibly as possible. We de-
veloped the project for a class of seventh grade children we taught in
1968-69 at the Huzzey Junior High School In Lexington, Mass** This was
the longest programming project these children had encountered, and our
intention was to give them a model of how to go about working under these
conditions. To achieve this purpose we ourselves worked very hard to
develop a clear organization of sub-goals which we exploLncd to the class
at the beginning of the 3 - veek period devoted to this particular program.
One would not expect beginners to find as clear a subgoal atructure as this
one; but once they have seen a good example, they are more likely to do so
in the future for other problems. Thus our primary teaching purpose was
to develop the idea of splitting a task Into sub-goals. We wanted the
children to have good models of various ways in which this can be done and
Co experience the heuristic power of this kind of planning (as opposed to
Jumping straight into writing programs).

Readers will notic© that the sub-goal structure divides the problem
in several ways. One way is by "chopping", that is to say, by recognizing
that the final program has distinct functions that can be performed by
separate sub-procedures. But this Is not the only way. Many heuristic

*This work was supported by NSF Contract No. H5F-C 558 to Bolt, Baranek
and Newman, Inc.

programs can bo "simplified" rather than "chopped". We illustrate this
by first writing a procedure to play the "whole game*', but in a "dumb
way". Once we have done so, we can study its performance* decide why
It plays badly and strengthen its play. Thus the successive partial
solutions to the problem appear as making a procedure progressively
"smarter".

Describing the evolution of the program in this way has the addition-
al benefit of allowing one to make an analogy with the way a child night
learn the game. We find this analogy valuable in two senses: by using
himself as a model the child acquires a fertile source of ideas about pro-
gramming; on the other hand, the experience of debugging programs can
have a therapeutic effect In leading his to see his own as emotionally
neutral bugs rather than as emotionally charged errors*

1,1 The Sub-Goal Plan

The key idea for subdivision of the problem is to write a series of
programs, each of which is "smarter" than the previous one. The first
program will know nothing about the strategy of play. It will not generate
moves, but ask each of two human player© in turn what move to make. For
example, it might act as a score-keeper , just keeping track of the number
of sticks without bothering about whether the move is legal. From score*
keeper the machine could advance to referee. This means that it checks
the moves for legality and eventually declares the game over and announces
the winner. After wc have a working mechanical referee we will start mak-
ing a mechanical player . The first version of a player will choose legal ,
but not necessarily good moves* Indeed, it will generate a move randomly ,
use its ability as a referee to decide if it is legal, and then either
accept it or generate another random move.

3XH-2

When this works, the child may make his program smarter and smarter by

adding features or by writing a ccrapletely new version until finally —

IT all goes well — an Infallible strategic player is evolved.

A natural form for programs of intermediate "smartness" is the

following; the program has a list of simple situations in which it

knows how to play; in other situations it plays randomly. In other

words, it plays by the form of strate©r used by most children in most

strategic games*

In working with a class, a good moment should be seized to prod
the children into noting and discussing -he analogy between thia
very simple heuristic program and themselves — particularly,
hew the program gets to be "smarter" through aore or through
better knowledge. Seeing the program as a cognitive model is
a valuable and exciting experience for the children. They can
easily be drown into discussion about how meaningful such models
are. To keep the discussion alive the teacher should be equipped
vith arguments and examples to counteract extremist, and so
sterile, positions. For example, if the children feel that the
program is too simple to be a model of human thinking, one might
discuss whether a toy airplane is a useful model of a Jet- liner.
Does it work by the same principles? Can one learn about air-
liners by studying toy models? On the other hand, if a class
swings over to the position that there really is no difference*
one could ask questions about whether the program could learn
by Itself without a programmer. But if this is too enthuaiaaxi-
cally accepted it is well to ask; hov much do you learn without
being told? Etc., etc. Ideally, the teacher should merely
guide the discussion without having to say any of this. But
awareness of such arguments will permit more sensitive guiding.
An interesting exercise and base for discussion is to have the
children stu^y various program of intermediate smartness,
classify their bad moves by degrees of stupidity, give the
programs grades or I.Q.'s (or say why they think <Joing so is
sillyl).

The stratification of the project has the good feature of allowing

children to find their own level. A slower child who gets only as far

as the random player, nevertheless, has the taste of success ^Xt his

program does what it does well. Tendencies to feel inferior should be

counteracted by the teacher's attitude and by encouraging individual

D1M-3

variations so that no child's final program la a mere subset of a more

advanced one. The teacher's computer culture can be very relevant in

this delicate kind of situation. Although the richness of programming

permits children to generate many fertile ideas, sensitive filtering by

the toachcr can enormously improve the achievement- to- frustration ratiou

Examples of individual frills to a referee, program : timing
moves, declaring the winner a move or Wo ahead ( I ) , allowing
a player to take a move back, printing a score sheet, giving
advice {I), allowing the players to be at two teletypes (if
the system permits), establishing and imposing handicaps (!} v
changing the rules, etc», etc.

2.0 Tho. Rules

A move consists of taking one, tvo or three aatch-sticks from
a given pile. Two players move alternately. Tho player who takes the
last stick vine.

3*0- First Steps with the Children

The first step is to see that everyone knows the rules and under-
stands what the first program will do; for example, by imitating its
function or by writing imaginary scripts. In the course of discussing
this ve would introduce ccae names (so as to be able to talk about what
wc are doingl).

WIK-I-

Example of a Script

TUB KWBER OF STICKS IS 8

JOK TO PLAY. WHAT'S YOUR MOVE?

THE HUMBER OF STICKS IS 6

BILL TO PLAY. WHAT'S YOUR W)VE!

*i

THE HUMBER OF STICKS IS 3

JOK TO PLAY. WHAT'S YOUR MOVE?

<3

JOH IS THE WXKNER,

Later in the project we insist that children consider what
happens when a player replies to "WHAT'S YOUR HOVE?" by "5"
or "COW"* Id the beginning ve would discourage all hut the
most competent children from worrying about "funny" answers
before getting the program to work with noraal answers.

Examining the script we see that there must be names for;

the current nianber of sticks — let's say "STICKS"

the wove — let's say "MOVE"

the next player — let's say "PIAYER"
and, a little more subtle

the other player — let's say "OPPOHEHT" .
To be sure that everyone understands wei have an assignment to fill in
these LOGOraiBGS for successive rounds following the previous script.

ROUND t :STICKS :PLAYER lOPPOSEFr :«OVE

1 8 "JOH" "BILL" 2

2 "JOB" 3

3 3

**.0. A Simple Score-keeper

If this is the first game-playing program, ve might give
the class an aliaost ready-made procedure. We build up
to it fcy asking seme standard Questions:

What shall ve call the procedure? (Let's say "HIMPLAY" )

What mist MIMPLAY dot

What must »B!PUY knew?

Possible answers are:

1* Announce the remaining number of sticks

3, Announce the player to move

3. Get his move and make all the modifications

I* • Recur -

To do this KIMPLAY must remember /STICKS , JPLAY2R , and : OPPONENT
from the previous round and get :HOVE by asking for it. The first
three THINGS must be told by one CTIMPLAY-GUY* to another, so they should
be inputs. On the other hand, :MOV£ comes from the human player, so
it can be gotten by REQUEST and need not be an input. If one looks ahead
one might notice that later on, 3MQVE vill sometimes cote from a procedure

*1be anthropomorphic metaphor is related to the little-men pictures In an
earlier section. The use of the antbropcororpMc language migt-t be a little
precious, but the concept of a separate agent for each program-call is
enormously valuable, Vtc children rijd not seem to resent terns Ifke r WK"

or n ctre n -

HIM- 6

— that is, when the machine gets to be smart enough to make Its own
oovea. Bo to keep the door open for changes, ve separate the problcmo

or Retting tMOVE and using it- The standard way to do this la to plan

on a cub-procedure ~ say, called "GETMOVE".

How ve can write NIMPLAY:
TO SIMPLAY :STICKS tPUYER ;OPFOHEST

1 PRIKT S EN T EN CE "TOE SUMBER OF STICKS IS" ISTICKS

2 PEIWT SBTCHJCE rPLAYEB "T^ PUT. WHAT'S YOUR HOVE?"
i HAKE ^ " — ~" ^T We pretend vc have

KAME "HEWSTICKS" \ already written

THISG :STICES - GBTKDVE \§EWOTE.

h fflMTLAY :l{SWSTICg& ;OPrCHEBT :PUYEE <~

nn>

Recursion line.

Notice how ;PIAYER

and :0?POffETCT arc

^reversed.

Tu GETUOVE

i MAKE

Ho input is necessary

MAKE

>KVS

THING REQUEST
2 OUTPUT :MOVE

CBIMWE's Job ia to
aake a new LOGOTHINQ.
So its main action is
this MAKE cocaaand.
It uses OUTPUT to
pass on what it

Rote the use of : STICKS -GETMOVE. We use infix notation as an option
in LOGO {with parentheses when needed to avoid ambiguity).

KIM- 7

A little-can picture of a round:

6 "BILL" "JOff M

HEXT \
niMPLAY \
GUY J

\

Cements: Notice the two-way line. The HIMPUlY-GUY called the
GBTMOVE-GUY expecting to get a LOGOTHIKG. So GETKOVE
must be an operation ; in other words It has an OUTPUT .
On the other hand, when one KIMPLAY-GUY calls the next
one he does not expect an answer: NIMPLAY is a ccusoand,
not an operation. So it has a one-way lins

MIM-B

5.0 Frca Scorg*keqyr to Referee

As referee the program has scene new tasks:
I* Decide vhetber the game is over
2. Declare the vinncr if it ia over

3- Make sure that iPIAYEH takes 1, £, or 3 sticks each tine'.
The first tasks arc achieved by adding a STOP-TEST line to KIMPLAY,
For example,

TEST IS :NE*ETICKS

iftrub pRnrr sEffrracs :player asd "is the winker"

IFTRUE STOP
The third task can be accomplished by giving GETMOVE a TRY-AGAIN form,

TO GETMOVE

1 PRINT " YOU MAY TAKE 1, 2, OR 3 STICKS"

2 MAKE

HAKE "MOVE"

THIEG REQUEST

3 TEST MEMBER :M0VB "1 2 3"

l\ IFPALSE OUTPUT GBTMOVE ^_ ■ 7 If the TEST is n FALSE n t try again,

5 OUTPUT :M0VE
EHD

With those changes filMPLAY is certainly a referee — hot still has
some rough edges. For example, when :STICKS is 2, GBTMOVE gives permis-
sion to take 1, 2, or 3 sticks! And if :PLAYE& takes 3, :STICKS become©
negative and the game vill go on forever on account of a SLIP-BY bug*
However, we shall leave it as an exercise to remedy these minor failings.

In presenting this section to children we might vork through one
of the two major modifications vith the class and let the children
struggle with the other. The SLIP-BY bug we would leave to the class
to discover and cure. Those who miss it at this stage will find
its presence more obtrusive later — and a profitable discussion
might develop on the question of why the bug was not found ~ per-
haps, because the human player always makes reasonable moves so that
:STICECS never becomes negative even though the oachine would allow
it. Later we shall sec that when Lhe machine makes its own moves
it will not be so cooperative unless we tell it to be.

HIM- 9

6,0. The Simplest Mechanical Player

Kov can the oachine choose a move? The simplest way is by using

RANDOM. For example, we could allow GETT-tOVE^the choice: if a person

is to pl*$r use BEQUEST, if the machine is to ploy use RANDOM. But it

has to be told whether the player is human or the ccroputer. So it oust

have an input.

TO GETMOVE ;PLAYER

TEST IS :PLAYER "COMPUTER"

IPrBUE HAKE

SAME "MOVE"
THING RANDOM
IPFAL8K PRINT "VOU MAY TAKE 1, 2, OR 3 STICKS"
IPFALSE KAKE

NAME: "MOVE"
TOIHG: REQUEST

(as before)

At this stage the SLIP-BY hug might beccae serious. One way to

to Kill It is to tell GETMOVE about :STICKS and have it try-again if

:H0VE comes up greater than rSTICKS . To do this we change the title

line to:

TO GETMOVE EPLAYKR 'STICKS

and add a pair of lines (in the TRY-AGAIN form) after the two MAKEs.

TEST GREATERP IMOVE (STICKS

JFiaUE OUTPUT GETMOVE :PLAYER :STICKS

«
Notice this anthropomorphism. We find it useful to talk of procedures

as agents, of their "state or knowledge," of "telling them" of having

them "talk to" one another. But we present thia to children as a

deliberate metaphor which they might find useful.

IXH-1Q

7.0. Strategic Play

Our plan for writing the SIM playing program in many strata now

calls for it to recognize a few special numbers and Know wh*tt to do in

those cases ♦ hut continue to ploy stupidly in other cases. However,

by this time it ia likely that the class has already discovered the

full strategy. It any still be worthwhile to encourage at least some

nenbcrc to follow the original plan as an instructive Joke. In this

section we shall illustrate a general question-answer technique for

classroom discussion and to encourage habits of heuristic neatness in
the children's own thinking.

7.1. A Senl-Saart KIM Player

A good exercise is to observe HIMPLAY In Its present condition, and
collect and classify its mistakes. An exasple of a classification made
by a child is:

RETARD MISTAKES: There were 2 or 3 sticks and the machine did

not take all)
DUMB M13TAKES: There were 5 sticks and the machine took 2. (If
the machine had any sense it would leave the opponent
with k.)

If there are 6 or 7 it'a dumb not to shoot for **.
We shall write a procedure to avoid first "retard mistakes" and then
"dumb mistakes".

Question: What program form7
Answer: TEST-TEST

Question: What do we test for?

English Answer: Whether there are l v 2, or 3 sticks,

LOGO Answer : TEST MEMBER :STICKS "1 2 3"

We recall the procedure MEMBER shown by the examples:

MEMBER 6 "1 2 3" =■ "FAIfiE"

MEMBER 2"12 3" = "TRUE"

Question: What is the action if the test is passed?

English Answer: Take all the sticks .

LOGO Answer: OUTPUT :STICKS

Question: What if it is not passed?

English Answer: Move Just like before,

LOGO Answer: MAKE

NAME "HOVE"
TH1HG RAfflXW

Putting this together to make a procedure to make the move:

Question: What must the procedure know?

Answer: rSTICKS — so it needs an input.

Question: Operation or command?

Answer: Operation, because it will give us :MOVE as its output.

TO MAKEMCVE :STICKS XAKEMOVE is an easy naz.c :.o

remember.
TEST MEMBER :STICKS "1 2 3"

IFTRUE OUTPUT :STICK5 The procedure is used in

IPFAL9E OUTPUT RANDOM place of RANDOM in GETMOVE>

EHD So don*t forget to change

GFD40VE1

How extra lines can be added- For example:
TEST IS rSTICKS "5"
I1TRUE OUTPUT "l"

NItf-12

7-2. Ike Ssiart Player

By this time everyone should be very close to understanding the
strategy* for exacple, in the following form:

Question: How does the game end?

Answer: When a player leaves zero sticks.
So let's try making the cain actor be the number of sticks we leave.
If we can leave zero that's great. But if we have more than 3 we can't.
So we must think ahead .

Question: What can we leave so as to help us leave zero next time?

Answer; k* Because the opponent will leave 1, 2, or 3*

Question: What can we leave so as to be able to leave U next time?

Answer: 6.
So 0, l*» 6 ore good numbers to shoot at for leaving.

Question: What others?

Answer: 12, 16, ...

Question: Describe these.

Answer: REMAINDER :OTM5ER: 4 ■

REMAINDER :CTUHBER :DIVIDER is an operation whose
output is the remainder when :?JUMBBR
is divided by : DIVIDER .

$6*i Question: If I give you a number called : NUMBER , how can
you use It to find the next number down divisible by

Answer: Subtract REMAINDER : NUMBER 4.

So there ve arcl The *mart Invincible KIMplsyer in made by replacing
KAKEHOVE by SMARTMOVE.

to smafwove : sticks

make <;—

SAME: n RIK"

THIKQ REMAINDER rSTICKS U
TEST IS jBSH
IFTRUE OUTPUT 1

<"

IFPALSE OUTFUT :REK

III*! 1

,

This LCGOTHIKG Is the coain
actor, so nase it-

v

It really doesn't matter
in this case.

HIM-1 1 *

8,0 F r i lls

Write supcrprocedurea or make additions to the present procedures so
that transcripts like the following vill be produced:

KIM

DO YOU KHOW HOW TO PLAY HIM?

*50

HERE ARE THE RULES: YOU WILL BE SHOWN A CLOOLECTIOR OK X'S, YOU HAY

REM3VE 1* 2 OR 3, THE PLAYER WHO TAKES THE LAST WIBS. THIS IS

PROBABLY TOO VAGUE FOB YOU TO UNDERSTATE), BUT TRY PLAYING AMD I'LL

CORRECT YOUR MISTAKES*

ARE YOU READY?

« I AM

PLEASE SAY "YES rt OR H H0"

4 JBS

OK, HOW TELL KE THE BAMS OF THE FIRST PLAYER*

<JM

SOW THE RAKE OF TUB OTHER PLAYER

< COMPUTER

HOW MASY STICKS DO YOU WANT TO START WITH?

< THIRTY

VK A DUMB COMPUTER. TYPE A PROPER HUMERAL.

«31

JOM TO PLAY.

THERE ARE 31 STICKS.

XXXXXXXXXXKXXXXXXXXXXXXXXXXXXXX

JOB. TAKE 1, 2 OR 3

<1

COMPUTER TO PLAY.
THERE ARE 26 STICKS.
X7XXXXXXXXXXXXXXXXXXXXXXXXXX
I TAKE 3

tTOH TO PLAY.

HiERE ARE 25 STICKS.

XXXXXXXXXXXXXXXXXXXXXXXXX

TAKE 1, 2 OR 3

<1

*

NIM-15

B.X Modifications

There are unlimited possibilities of "playing with" the ideas in
the procedure after it has been made to work. The following three are
merely examples to illustrate the idea that the project has not neces-
sarily run out when the procedure is debugged.

An interesting simple modification to the rule of the game is to
change the 1-2-3 rule to a 1-2 rule or a 1-2-3-4-5 rule. Write a pro-
cedure which will ask what rule is to be used.

Our stop rule was: the player who takes the last stick wins. Change
this to: he who cakes the last stick loses. (The latter is the traditional
form; meeting a temporary change could be considered as port of planning for
the project; students should be able to see and formulate the idea that our
rule leads to a simpler algorithm without changing its principle.)

The game can be embedded in a more complex one, such as moving coun-
ters along marked paths on a board. If there is just one linear path, the
problem is identical, but if branches are allowed, interesting complexities
arise.

BD4-16

APPBDIX

A Listing; of the RIMPLAY Pra^d^res

TO HIMPLAY : STICKS : PLAYER : OPPONENT

10 PRDIT SEKTENCE "THE KUMBER OF STICKS IS" AHD : STICKS

20 PRIHT SEHTEKCE : PLAYER ABD

30 MAKE

MAKE "HEWSTICKS"

THIHG :STICKS - GEBWVE :PLAYER :STICKS
iiO TEST IS :HEWSTICK5

50 IFTRUE PRIKT SEJ!TE??CE rPLAYER ARD "IS THE WITfHER"
60 IFTRUE STOP
70 HIMPIAY rHEVSTICKS :GPPOHEtfT rPLAYER

TO GBTHOVE : PLAYER : STICKS

10 TEST IS :PLAYER "COMPUTER"

30 IFTRUE MAKE

HAME "MOVE"

THIHG SMARTMOVB
30 IFFALSE PRIHT "YOU MAY TAKE 1* S t OR 3 STICKS"
bo IFFALSE HAKE

SAME "MOVE"
THIHG REQUEST
50 TEST MEMBER :MOVE "1 2 3"
60 IFFALSE OUTPUT GETWOVE ;PLAYER :STICKS
70 TEST GREATERP :MOVE rSTICKS
80 IFTRUE OUTPUT GEIHOVB :PLAYER :STTCKS
90 OUTPUT ;KOVE

TO SMARTMOVE
10 MAKE

HAME "REM"

THING: REMAINDER :STICKS 4
TEST IS :REH
20 IPTItUE OUTPUT I
30 IFFALSE OUTPUT :RfH
BCD

N1M-17

We include a listing of MEMBER, but assume that it was written before
the NIM unit.

TO MEMBER :IT :LIST

10 TEST IS :LIST :EHPTY

20 IFTRUE O0TPUT "FALSE"

30 TEST IS :IT FIRST :LIST

40 IFTROE OUTPUT "TRUE"

50 OUTPUT MEMBER :1T BUTFIRST :LIST